package dp;

import java.util.Arrays;

public class Solution {
    //两个字符串删除
    public static void main(String[] args) {
        System.out.println(minDistance("park", "spake"));
    }

    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for (int i = 1; i < m + 1; i++) {
            char x = word1.charAt(i - 1);
            for (int j = 1; j < n + 1; j++) {
                char y = word2.charAt(j - 1);
                if (x == y) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Integer.max(dp[i][j], max);
                } else {
                    dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        print(dp);
        return word1.toCharArray().length - max + word2.toCharArray().length - max;
    }

    private static void print(int[][] dp) {
        System.out.println("=====");
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("=====");
    }
}
